#include <vector>
#include <iostream>

using namespace std;

/**
 * Single Link List
 */
class Node {
public:
  int value;
  Node *next;

  Node(int v, Node *p = nullptr) : value(v), next(p) {
    cout << "A Node is created." << endl;
  }
};

// 1 -> 2 -> 3 -> 4 -> nullptr
class SingleLinkList {
public:
  // 添加一个叫做 size 的属性，表达链表中的元素个数
  // 对构造函数进行对应的修改
  Node *head;
  int size;

  SingleLinkList(Node *h = nullptr) {
    cout << "A SingleLinkList is created." << endl;
    if (h == nullptr) {
      size = 0;
    }
    else {
      size = 1;
    }

    head = h;
  }

  // 返回链表中位置 pos 的节点
  // getNode(-1)
  // size 元素个数
  // 0, 1, 2, 3, ..., size - 1
  Node *getNode(int pos) {
    if (pos < 0 || pos >= size) {
      return nullptr;
    }

    Node *p = head;
    for (int i = 0; i < pos; ++i) {
      p = p->next;
    }

    return p;
  }

  // 数据结构的四个基本操作：增、删、改、查
  // 向链表的某个位置，添加一个元素
  // 0    1    2    3
  // 1 -> 3 -> 5 -> 7 -> nullptr
  //      p    c
  // newNode->next = c;
  // p->next = newNode;
  // addAtIndex(2, 9);
  // 原始链表中，哪些位置的节点和这个添加操作有关？
  // 1 和 2
  // 1 -> 3 -> 9 -> 5 -> 7 -> nullptr
  // 为了在位置 pos 插入一个值，哪些位置和添加操作有关？
  // pos - 1 和 pos
  // Node *prev;
  // Node *curr;
  // addAtIndex(-1, 10);
  //  0     1     2     3     4
  // 20 -> 11 -> 12 -> 13 -> nullptr
  // addAtIndex(0, 20)

  void addAtIndex(int pos, int value) {
    if (pos < 0 || pos > size) {
      return;
    }

    Node *add = new Node(value);

    if (pos == 0) {
      Node *curr = head->next;
      head->next = add;
      add->next = curr;
    }
    else {
      // 下面这些代码，只适用于 pos > 0 的情况
      Node *prev = getNode(pos - 1);
      Node *curr = prev->next;
      prev->next = add;
      add->next = curr;
    }

    ++size;
  }

  // 01-28 作业
  // 实现 printList 方法，按照下面的格式打印链表的所有节点
  // 1 -> 2 -> 3 -> 4 -> nullptr
  void printList() {
    //
  }
};

int main(int argc, char const *argv[])
{
  /* code */
  Node p1 { 10 };
  Node *p2 = new Node(11);

  SingleLinkList sll; // head -> nullptr, size = 0
  SingleLinkList s1(p2); // head -> 11, size = 1

  // 01-28 作业，在 main 函数里，验证 printList 的结果。
  return 0;
}
